(1) Field of the Invention
This invention relates to a divider unit for executing a division in which a dividend and a divisor are both fixed-point parts of a floating-point number or a division in which a dividend and a divisor are both fixed-point numbers, the divider unit being applied in an information processor or the like.
(2) Description of the Related Art
Recently, an operation unit for executing high-speed floating-point operation has been demanded in a lot of information processing fields such as signal processing and numerical calculation.
A division procedure generally takes much longer than an addition, subtraction or multiplication procedure. Executing such division procedure at a high speed cannot be realized without a huge-scale hardware.
Ever since a computer was first developed, division algorithms have been actively researched in order to obtain a divider unit for executing a high-speed division with simple hardware. Some of the algorithms which have been developed so far are mentioned in:
1) Kai Hwang, "Computer Arithmetic/Principles, Architecture, and Design," John Wiley & Sons, 1980;
2) D. E. Atkins, "Higher-Radix Division Using Estimates of the Divisor and Partial Remainders," IEEE Transactions on Computers, Vol. C-17, No. 10, pp. 925-934, Oct. 1968; and
3) D. E. Atkins, "Design of the Arithmetic Units of ILLIAC III: Use of Redundancy and Higher Radix Methods," IEEE Transactions on Computers, Vol. C-19, No. 8, pp. 720-733, Aug. 1970.
According to the above publications, a quotient Q.sub.n (to be obtained by dividing a dividend R.sup.(0) by a divisor d) and a value R.sup.(n+2) (to be obtained by multiplying a final remainder by 2.sup.j ; j=a multiple of two) are obtained by executing the following algorithm. The quotient Q.sub.n has a bit length of n (n=a multiple of two) to the right of the binary point. R.sup.(n+2) will be referred to simply as the final remainder, hereinafter.
The following algorithm is a radix-4 case. In other words, the quotient Q.sub.n is obtained two digits by two digits. Each two digits are at the j-1'th and the j'th binary places in the binary representation and form a quotient digit q.sub.j. A quotient from the first to the j'th binary places is referred to as Q.sub.j.
A value obtained by multiplying a partial remainder by 2.sup.j is represented by R.sup.(j). R.sup.(j) is used to obtain the quotient digit q.sub.j and will be referred to simply as the partial remainder, hereinafter. The value at the i'th binary place of the partial remainder R.sup.(j) expressed in the two's complement representation is referred to as A.sub.i. A value at the i'th binary place of the divisor d is referred to as M.sub.i. In summary, EQU R.sup.(j) =A.sub.0.A.sub.1 A.sub.2 A.sub.3 A.sub.4. . . EQU Q.sub.j =q.sub.0.q.sub.2 q.sub.4. . . q.sub.j EQU d=0.M.sub.1 M.sub.2 M.sub.3 M.sub.4. . .
where A.sub.0 indicates a sign in the two's complement representation.
The partial remainder R.sup.(j) and the quotient digit q.sub.j are expressed in the redundant binary representation. In other words, each digit in the binary representation is expressed by two bits: a sign bit and an absolute value bit.
______________________________________ &lt;Step 1&gt; Normalize the dividend R.sup.(0) and the divisor d as follows: 2.sup.-1 .ltoreq.R.sup.(0) &lt;1 2.sup.-1 .ltoreq.d&lt;1 If normalization has already been done, this step is not necessary. &lt;Step 2&gt; q.sub.0 :=[01].sub.2 ; Q.sub.0 :=q.sub.0 ; R.sup.(2) :=R.sup.(0) -q.sub.0 .multidot.d; &lt;Step 3&gt; for j:=2 to n+1 step 2 do begin Select a quotient digit q.sub.j in accordance with FIGS. 1 and 2. R.sup.(j+2) :=4R.sup.(j) -q.sub.j .multidot.d; Q.sub.j :=Q.sub.j-2 +q.sub.j .multidot.2.sup.-j ; end &lt;Step 4&gt; if R.sup.(n+2) &lt;0 then begin Q.sub.n :=Q.sub.n -2.sup.-n R.sup.(n+2) :=R.sup.(n+2) +d; end &lt;Step 5&gt; ______________________________________
Convert the quotient Q.sub.n into the two's complement representation. If necessary, convert the final remainder R.sup.(n+2) into the two's complement representation.
The above description is conformed to the Pascal program language. ":=" is an operator indicating substitution, and "[. . .].sub.2 " indicates the value in the bracket is expressed in the binary representation. Step 3 is repeated, in which each round will be referred to as a loop in this specification.
FIG. 1 shows a divisor interval selection logic for selecting one interval which a divisor d belongs to out of a plurality of intervals bordered by specified values. Variables D.sub.1 through D.sub.11 represent the operation results obtained by the logical expressions shown in FIG. 1. Only one of the variables D.sub.1 through D.sub.11 is set to be 1.
FIG. 2 shows a quotient digit selection logic for selecting a quotient digit q.sub.j based on the variables D.sub.1 through D.sub.11 and the partial remainder R.sup.(j). Variables zeroP, etc. represent the operation results obtained by the logical expressions shown in FIG. 2. Only one of the variables is set to be 1, and the corresponding quotient digit to the above one variable is selected.
In FIGS. 1 and 2, each bar above the variable means logical NOT. In FIG. 2, each bar above the figure in the quotient digit column indicates that the figure below the bar is negative. For instance, 1 means -1.
FIG. 3 is a block diagram of a conceivable divider unit 100 for executing a division using the above algorithm.
1 refers to a divisor interval selection circuit for selecting one interval which the divisor d belongs to out of a plurality of intervals bordered by specified values based on M.sub.2, M.sub.3 and M.sub.4 in accordance with FIG. 1.
3 refers to a quotient digit selection circuit for selecting one value as a quotient digit q.sub.j out of values -2, -1, 0, 1 and 2, of which absolute values are each represented in two bits. The selection is done based on the selection result of the circuit 1 and A.sub.0 through A.sub.6 in accordance with FIG. 2. A.sub.0 through A.sub.6 are obtained from a partial remainder R.sup.(j) outputted by a subsequent partial remainder generation circuit 17 (will be described later in detail). A.sub.0 is a sign of a value obtained by converting the upper six digits of the partial remainder R.sup.(j) into the two's complement representation. A.sub.1 through A.sub.6 are values at the first through the sixth binary places of the above value. The circuit 3 is to output a value 1 as a quotient digit q.sub.0 on an initial stage of the division. The circuit 3 is also to send a selection command to a divisor's multiple selection circuit 13 (will be described later in detail) and an addition/subtraction command to a subsequent partial remainder generation circuit 17.
4 refers to a positive quotient digit storage circuit for storing the absolute value of the quotient digit q.sub.j if the quotient digit q.sub.j selected by the circuit 3 is positive and storing a value 0 if not. Either value is stored at a digit position corresponding to the loop in which the storage is executed.
5 refers to a negative quotient digit storage circuit for storing the absolute value of the quotient digit q.sub.j if the quotient digit q.sub.j is negative and storing the value 0 if not. Again, either value is stored at a digit position corresponding to the loop in which the storage is executed.
6 refers to a quotient conversion circuit for subtracting the value of the circuit 5 from the value of the circuit 4, whereby to output the subtraction result as a quotient Q.sub.n.
10 refers to a divisor's double generation circuit for generating the double of the divisor d.
The divisor's multiple selection circuit 13 is for outputting the product of the absolute value of the quotient digit q.sub.j and the divisor d (namely, the divisor d, the double of the divisor d or 0) in response to the selection command from the circuit 3.
16 refers to a partial remainder's quadruple generation circuit for generating the quadruple of the partial remainder R(j) sent from the subsequent partial remainder generation circuit 17.
The subsequent partial remainder generation circuit 17 is for subtracting the divisor d from a dividend R.sup.(0), both normalized by a normalization circuit (not shown), and outputting the subtraction result as a first partial remainder R.sup.(2) on the initial stage of the division. The circuit 17 is then to subtract the value sent by the circuit 13 from the quadruple of the partial remainder R.sup.(j) if the quotient digit q.sub.j is positive and add the above value and the above quadruple if the quotient digit q.sub.j is negative, in response to the addition/subtraction command from the circuit 3.
The above addition and subtraction are done in the redundant binary scheme, and the partial remainder R.sup.(j) is also obtained in the redundant binary representation.
The divider unit 100 having the above construction executes the division in the following way.
1) When the normalized dividend R.sup.(0) and divisor d are inputted, the subsequent partial remainder generation circuit 17 subtracts the divisor d from the dividend R.sup.(0) and outputs the first partial remainder R.sup.(2). The quotient digit selection circuit 3 outputs the value 1 as the quotient digit q.sub.0 (the value at ones place in the binary representation) and stores the above value 1 in the positive quotient digit storage circuit 4.
2) The divisor interval selection circuit 1 decodes M.sub.2 through M.sub.4 in accordance with FIG. 1 and then selects the interval which the divisor d belongs to. Such selection is done only once on the initial stage of the division, and the selection result is retained until the division is finished.
3) The quotient digit selection circuit 3 converts the upper six digits of the first partial remainder R.sup.(2) sent by the circuit 17 into the two's complement representation, thereby obtaining A.sub.0 through A.sub.6. Based on A.sub.0 through A.sub.6 and the selection result of the circuit 1, the circuit 3 selects one value as a quotient digit q.sub.2 out of -2, -1, 0, 1 and 2 in accordance with FIG. 2 and outputs the selected value. As mentioned before, the values -2, -1, 0, 1 and 2 each have an absolute value represented in two bits.
4) On receiving the quotient digit q.sub.2 from the circuit 3, the positive quotient digit storage circuit 4 stores the absolute value of the quotient digit q.sub.2 at a digit position in the circuit 4 if the quotient digit q.sub.2 is positive, the digit position corresponding to a first loop. If the quotient digit q.sub.2 is not positive, the circuit 4 stores 0 at the same digit position.
On the contrary, the negative quotient digit storage circuit 5 stores the absolute value of the quotient digit q.sub.2 at a digit position in the circuit 5 if the quotient digit q.sub.2 is negative, the digit position corresponding to the first loop. If the quotient digit q.sub.2 is not negative, the circuit 5 stores 0 at the same digit position.
5) The divisor's multiple selection circuit 13 outputs the product of the absolute value of the quotient digit q.sub.2 and the divisor d in response to the selection command from the circuit 3.
6) On receiving the addition/subtraction command from the circuit 3, the subsequent partial remainder generation circuit 17 subtracts the value sent by the circuit 13 from the quadruple of the partial remainder R.sup.(2) if the quotient digit q.sub.2 is positive and adds the above value and the above quadruple if the quotient digit q.sub.2 is negative, whereby outputting a second partial remainder R.sup.(4). Then, the operation goes back to 3) for the next loop, wherein R.sup.(4) is used instead of R.sup.(2).
7) The above 3) to 6) is repeated n/2 times (the figures in binary places are counted as one) while incrementing each superscript and subscript by two. In this way, each quotient digit q.sub.j is obtained in the redundant binary representation, and the quotient digit q.sub.j is stored in the circuit 4 or 5 depending on the sign thereof. Then, a final remainder R.sup.(n+2) is outputted from the circuit 17.
8) The quotient conversion circuit 6 subtracts the value stored in the circuit 5 from the value stored in the circuit 4 and converts the subtraction result into the two's complement representation. If the final remainder R.sup.(n+2) is negative, the circuit 6 subtracts a value 1 at the lowest bit of the above subtraction result in the two's complement representation, whereby the quotient Q.sub.n is obtained. If necessary, the circuit 6 also converts the final remainder R.sup.(n+2) into the two's complement representation in the same manner by a final remainder compensation circuit (not shown), and if the obtained value is negative, adds the divisor d thereto.
In the above divider unit 100, the times the operation of the loop is repeated is approximately as half as in other types of divider units which are designed to execute the SRT division of radix-2 cases or the nonrestoring division. Further, since the subsequent partial remainder generation circuit 17 is controlled to operate in the redundant binary scheme, which requires no carry propagation, the operation time of each loop is shortened. As a result of the above two advantages, the above divider unit 100 executes the division nearly twice as fast as the above other types of divider units.
In a divider unit designed to execute the SRT division of radix-4 cases, the quotient digit is selected out of -3, -2, -1, 0, 1, 2 and 3. In the above divider unit 100, on the other hand, the quotient digit is selected only out of -2, -1, 0, 1 and 2. Accordingly, the circuit for obtaining the product of the quotient digit and the divisor comprises only two circuits: the divisor's double generation circuit 10 and the divisor's multiple selection circuit 13. As a result, simple hardware and high-speed execution are realized.
However, the above divider unit 100 has the following problem. The quotient digit selection logic is complicated enough to require a quotient digit selection decoder for decoding a lot of upper bits of the partial remainder and the divisor. The addition of such a decoder enlarges the hardware of the quotient digit selection circuit 3 and prolongs the quotient digit selection time.
Moreover, application of the above divider unit 100 to higher-radix division of radix-8 or more is quite impossible because such application would further complicate the quotient digit selection decoder and prolong the quotient digit selection.